package life;

import java.util.Stack;

// 大数求和
public class BigAdd {


    public static void main(String[] args) {
        System.out.println(add("16", "678"));
    }
    /**
     * 思想就是：
     * 1、把两个数的 各个位 从高到低 挨个入栈。
     * 2、
     */
    public static String add(String a, String b) {
        // 1、
        Stack<String> sa = stringToStack(a);
        Stack<String> sb = stringToStack(b);
        int tSum = 0; // 两位数的和
        boolean isCarry = false; // 是否有进位
        Stack<String> sum = new Stack<>();

        // 2、
        while (!sa.isEmpty() && !sb.isEmpty()) {
            tSum = Integer.parseInt(sa.pop()) + Integer.parseInt(sb.pop());

            if (isCarry) {
                tSum++;
                isCarry = false;
            }
            if (tSum >= 10) {
                tSum -= 10;
                isCarry = true;
            }
            sum.push(tSum + "");

        }
        // 3、
        Stack<String> temp = !sa.isEmpty() ? sa : sb;
        while (!temp.isEmpty()) {
            int t = Integer.parseInt(temp.pop());
            if (isCarry) {
                t++;
                if (t >= 10) {
                    t -= 10;
                } else {
                    isCarry = false;
                }
            }
            sum.push(t + "");

        }
        if (isCarry) {
            sum.push("" + 1);
        }

        // 4、遍历输出sum栈即可
        String res = "";
        while (!sum.isEmpty()) {
            res += sum.pop();
        }
        return res;

    }

    private static Stack<String> stringToStack(String s) {
        Stack<String> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                stack.push(s.charAt(i) + "");
            }
        }
        return stack;
    }


    // 另一种方法
    public String addStrings(String num1, String num2) {
        int i = num1.length() - 1, j = num2.length() - 1, add = 0;
        StringBuffer ans = new StringBuffer();
        while (i >= 0 || j >= 0 || add != 0) {
            int x = i >= 0 ? num1.charAt(i) - '0' : 0;
            int y = j >= 0 ? num2.charAt(j) - '0' : 0;
            int result = x + y + add;
            ans.append(result % 10);
            add = result / 10;
            i--;
            j--;
        }
        // 计算完以后的答案需要翻转过来
        ans.reverse();
        return ans.toString();
    }
}
